Biclique-colouring is a colouring of the vertices of a graph in such a waythat no maximal complete bipartite subgraph with at least one edge ismonochromatic. We show that it is coNP-complete to check whether a givenfunction that associates a colour to each vertex is a biclique-colouring, aresult that justifies the search for structured classes where thebiclique-colouring problem could be efficiently solved. We considerbiclique-colouring restricted to powers of paths and powers of cycles. Wedetermine the biclique-chromatic number of powers of paths and powers ofcycles. The biclique-chromatic number of a power of a path P_{n}^{k} is max(2k+ 2 - n, 2) if n >= k + 1 and exactly n otherwise. The biclique-chromaticnumber of a power of a cycle C_n^k is at most 3 if n >= 2k + 2 and exactly notherwise; we additionally determine the powers of cycles that are2-biclique-colourable. All proofs are algorithmic and provide polynomial-timebiclique-colouring algorithms for graphs in the investigated classes.
展开▼
